1. Field of the Invention
The present invention relates to a weighted secret sharing and reconstructing method, and more particularly, to a method of sharing and reconstructing a secret using a weighted error vector.
2. Description of the Related Art
When there are a set R of N participants and a set L of subsets of the N participants, a threshold secret sharing scheme distributes shares of a secret to the N participants and allows the secret to be reconstructed when subsets of participants belong to the set L.
An ideal threshold secret sharing scheme has the following characteristics: (i) all participants must take part in key agreement of the set R; (ii) a master private key of the set R is not disclosed to all the participants; (iii) at least a predetermined number (i.e., a threshold) of participants must participate in a process of decrypting a message encrypted by the master private key; (iv) at least a predetermined number (i.e., a threshold) of participants must participate in a signature procedure of the message using the master private key; (v) after setting the scheme, the process of decryption or signature of the message by the participants whose subsets belong to the set L is non-interactive; and (vi) the master private key or a public key shall not be changed even when a new participant is included in the set R or a participant belonging to the set R leaves the set R.
A (k,N) threshold secret sharing scheme is another example of the threshold secret sharing scheme. The (k,N) threshold secret sharing scheme allows a secret to be reconstructed when k of N dispersed secret shares are collected. FIG. 1 illustrates a a conventional (k,N) threshold secret sharing scheme. Referring to FIG. 1, a secret 10 is divided into secret shares with equal importance and distributed to N participants 11. The secret 10 is reconstructed by collecting the secret shares of at least three of the N participants, combining them (see reference numeral 12), and reconstructing a secret 13.
However, the (k,N) threshold secret sharing scheme is disadvantageous in that at least k secret shares are required to reconstruct a secret since N secret shares with equal importance are distributed to N participants. For instance, it is impossible to completely reconstruct the secret when (k−1) secret shares are collected and combined.
Alternatively, a hierarchical threshold secret sharing scheme, which is yet another example of the threshold secret sharing scheme and allows each level of a multi-level structure to share a secret, needs to give a hierarchical grant to a participant who desires to access the multi-level structure.